import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Text {

    /** 四个数的和
     *  和三数之和同理
     */
    public List<List<Integer>> fourSum(int[] nums, int target) {
        Arrays.sort(nums);
        List<List<Integer>> lists = new ArrayList<>();
        for (int a = 0; a < nums.length; ) {
            for (int b = a + 1; b < nums.length;) {
                int left = b + 1;
                int right = nums.length - 1;
                long poor = (long)target - nums[a] - nums[b];
                while (left < right){
                    if(nums[left] + nums[right] > poor){
                        right--;
                    } else if (nums[left] + nums[right] < poor) {
                        left++;
                    }else {
                        List<Integer> list = new ArrayList<>();
                        list.add(nums[left]);
                        list.add(nums[right]);
                        list.add(nums[a]);
                        list.add(nums[b]);

                        lists.add(list);

                        left++;
                        right--;
                        while (left < right && nums[left] == nums[left-1]){
                            left++;
                        }
                        while (left < right && nums[right] == nums[right+1]){
                            right--;
                        }
                    }
                }
                b++;
                while (b < nums.length && nums[b] == nums[b-1]){
                    b++;
                }
            }
            a++;
            while (a < nums.length && nums[a] == nums[a-1]){
                a++;
            }
        }
        return lists;
    }

    /** 三个数的和
     * 借用了两个数的和
     * 先排序，然后用两个数之和
     *
     */
    List<List<Integer>> list = new ArrayList<>();
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        for(int i = 0;i < nums.length;){
            if(nums[i] > 0){
                break;
            }
            int left = i + 1;
            int right = nums.length - 1;
            while(left < right){
                if(nums[left] + nums[right] > -(nums[i])){
                    right--;
                } else if (nums[left] + nums[right] < -(nums[i])) {
                    left++;
                }else {
                    ArrayList<Integer> list1 = new ArrayList<Integer>();
                    list1.add(nums[i]);
                    list1.add(nums[left]);
                    list1.add(nums[right]);

                    list.add(list1);
                    left++;
                    right--;
                    while (left < right && nums[left] == nums[left-1]){
                        left++;
                    }
                    while (left < right && nums[right] == nums[right+1]){
                        right--;
                    }
                }
            }
            i++;
            while (i < nums.length && nums[i] == nums[i-1]){
                i++;
            }
        }
        return list;
    }



    /** 和为s的两个数
     *  使用单调性 双指针来找到这两个数。
     */

    public static int[] twoSum(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while (left < right){
            if(nums[left] + nums[right] > target){
                right--;
            } else if (nums[left] + nums[right] < target) {
                left++;
            }else {
                return new int[]{left,right};
            }
        }
        return new int[]{ 0 };
    }


    /**
     * 有效的三角形个数
     * 三角形的必要条件是：任意两条边加起来 大于 第三边
     * 但是我们也知道 如果两个小边之和大于第三边那么这也是个三角形
     * 所以 我们可以先给这个数组排个序，然后固定最长边，根据双指针来计算有多少个三角形
     * @param nums
     * @return
     */
    public static int triangleNumber(int[] nums) {
        int ret = 0;
        //先让这个数组有序
         Arrays.sort(nums);

        for (int i = nums.length - 1; i >= 2; i--) {
            int left = 0;
            int right = i - 1;
            while (left < right){
                if(nums[left] + nums[right] > nums[i]){
                    ret += right - left;
                    right--;
                }else {
                    left++;
                }
            }
        }
        return ret;
    }

    public static void main(String[] args) {
//        int[] array = {2,2,3,4};
        int[] array = {3,2,4};
//        System.out.println(triangleNumber(array));

        int[] ret = twoSum(array,6);
    }
}
